<?php

/**
 * 插入排序: 将无序的一个或几个记录“插入”到有序的序列中.
 * 插入排序的时间复杂度是 O(n^2)，它是稳定的排序
 */
function InsertSort($arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) { // 开始循环，从第二个元素开始，下标为 1 的
        $tmp = $arr[$i]; // 取出未排序序列第一个元素
        //// 判断从当前下标开始向前判断，如果前一个比当前元素大
        for ($j = $i; $j > 0 && $arr[$j - 1] > $tmp; $j--) {
            $arr[$j] = $arr[$j - 1]; // 依次移动元素
        }
        // 将元素放到合适的位置
        $arr[$j] = $tmp;
    }
    return implode(', ', $arr);
}

$numbers = [49, 38, 65, 97, 76, 13, 27, 49];
echo "原始数据: " . implode(', ', $numbers), PHP_EOL;
echo "插入排序结果: " . InsertSort($numbers), PHP_EOL;
//13, 27, 38, 49, 49, 65, 76, 97